//
// Created by user on 2022/3/15.
//

#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
    };
ListNode* reverse(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* curr = head;
    while (curr) {
        ListNode* next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}
//回文列表
bool isPalindrome(ListNode* head) {
    //
    if(!head || !head->next)return true;

    //快慢指针
    ListNode *slow = head;
    ListNode *fast = head->next;
    while (fast && fast->next){
        slow = slow->next;
        fast = fast->next->next;
    }
    //截成两段
    ListNode *newHead = slow->next;
    slow->next = nullptr;

    ListNode *left = head;
    ListNode *right = reverse(newHead);

    while(right) {
        if (left->val != right->val) {
            return false;
        }
        left = left->next;
        right = right->next;
    }
    return true;
}